The present invention relates to the field of searching for physical entities or devices and more particularly to a method for grouping such physical entities or devices in a topological or physical space.
In various applications, it becomes necessary to select an entity or various entities from a pool of entities to perform certain tasks within a topological area. For example, in cellular phone communications, it is necessary to determine which node is the appropriate node to carry a particular signal when the cellular phone user travels from place to place. To track the user, the cellular phone system can poll each and every node that it controls to determine which node is appropriate for the present location of that user.
Another example of locating physical entities in a physical space arises from the desire to include sensors or physical data sensing devices in fields or other open spaces where they can be used to detect various types of activities. These data sensing devices may be located in an area if possible military activity and be positioned to detect targets, such as tanks, trucks, helicopters, or even people. At the present, such devices tend to be quite expensive and quite large. The expense presents a problem as at least three such data sensing devices are needed for accurate location of any activity and, in case one of these is defective or becomes destroyed, at least one other standby must have been positioned to allow for continued receipt of sensing data. Obviously, the more such sensing devices that can be placed out in the field, the more accurate and the better the collection of data on whatever activity is to be observed. The size becomes a problem as in most instances it is desirable that for whatever activity that is being observed. Finally, present such devices tend to work only in flat or open spaces and not in an environment such as brush or forest.
It is therefore advantageous that the data sensing devices to be placed out in the field should be small, cheap enough to be entirely expendable, and not be active devices that could alert whoever is engaged in the activity to be observed that they are being observed. However, problems arise with the handling of such a large number of sensing devices. The problems involve the selection process for determining which groups of devices are to be active at a given time. It is therefore necessary to segment or section up the space both in terms of the space it self and the groupings of the sensor devices.
In general, such a selection process can be made more efficient by limiting the number of entities that will be searched. The distribution of entities in a topographical space allows for a grouping of the entities on the basis of location. The search and selection process becomes more complex when there are a number of entities distributed in a topological space which utilize different methods to perform their tasks and have differing ranges of effectiveness. The range of effectiveness of an entity for a specific function can be referred to as the entity""s footprint. Specific applications can concentrate on only one method of performing a task or what can be referred to as the morphology of the entity. By concentrating on one particular morphology, the application can omit entities that perform the same function, albeit by a different method.
For example, in tracking a particular traveling object, different detection methods can include infrared, RF and visual morphologies. Concentration on only infrared methods of tracking this object can exclude a RF detector that can achieve the function of tracking that particular object. In other instances, depending on the type of object being tracked, visual detection might be unable to track the object while RF detection will accomplish that function. Thus, visual detection exists in a different functional domain than the RF detector. In addition, two different entities might utilize the same method of detection, but still have different functional domains. For example, light detectors might have different frequency ranges which would create different functional domains if the object being detected were light of a specific frequency.
Choosing a subset of entities from the whole set is a combinatorial optimization problem. Almost all the relevant classes of combinatorial optimization problems are NP hard. NP hard problems typically lead to time-consuming searches. Reducing this search space becomes a requirement when there is a time constraint in selecting appropriate entities.
The distribution of entities in a topographical space allows for a separation of these entities on the basis of location. Space partitioning methods based on topology of morphologically different entities and Binary Space Partitioning Trees techniques are useful in limiting the areas of search based on location. In the case of the former, only the partitioning of physical space is considered for better packing of physical objects in a limited space. In the latter, search space partitioning is performed by the separation of entities that are all of different types (there is no distinction between functional and morphological characteristics and there is no concept of physical space). This invention is concerned with the functional partitioning of entities based on the type of objects the entity responds to in a physical space.
This invention utilizes standard physical space partitioning techniques along with entity characteristics to distribute them into limited size overlapping sets. Partitioning is performed based on the functionality and location of the entity rather than on the morphology of the entity. A membership value, ranging from 0 to 1, is assigned to each entity associated with each set resulting in fuzzy characteristics for the sets. Dynamic variation in the range of effectiveness of the entity is accounted for by changing the memberships of the entities to the groups based on the varying range of effectiveness. A metric can be derived from the membership value list of each entity to enable a unique single dimensional comparison of two disparate entities that are described in many dimensions.
The procedure of partitioning, in summary, is the following: a distribution of the entities in a topographical space is provided as input. The input includes the type and functionality of each entity. Further, the variation of the entity range of effectiveness is input.
First, separate grids are created for each functional attribute of the entities. The grid spacing is an independent parameter that is loosely tied to the range of the functional attribute of the particular grouping of entities. If the ranges of separate types of entities for the same functional characteristics are unequal, the smaller range is selected. The spacing parameter can be, and is, changed if required.
For each grid space of each functional attribute a fuzzy set is created. All those entities of the particular functional attribute whose range of effectiveness overlap a portion of a grid space are assigned to be members of the particular fuzzy set associated with the grid space. The membership value of the entity to that group is determined. This procedure is completed for the entire group of entities that exist in the particular space. A change in the footprint of an entity results in the entity initially being removed from membership of all groups. The assignation is then recomputed based on the aforementioned procedure.
In accordance with one embodiment of the invention, a method for dynamically grouping limited range entities in a topological space is disclosed where the method comprises the steps of: determining functional domains for each entity in the topological space; partitioning the topological space into grids wherein the partitioning step is performed on the topological space for each different functional domain that exists; associating a group with each grid that corresponds to a unique functional domain and unique topological space; ascertaining a range of effectiveness for each entity wherein the ascertaining step is performed for each functional domain to which an entity belongs; comparing the range of effectiveness of each entity with each grid space that is associated with each group for each functional domain that the entity and group share in common; assigning each entity to be a member of each group whose compared range of effectiveness intersects the compared grid space that is associated with the group; and storing the group memberships of each entity.
In accordance with another aspect of this embodiment of the invention, the method further comprises the steps of: identifying when a change of conditions for any entity occurs; the conditions including a change in function, a change in range of effectiveness and a change in location; and repeating the ascertaining, comparing, assigning and storing steps when the change occurs.
In accordance with another aspect of this embodiment of the invention, the grid dimensions for each functional domain correspond to the smallest range of effectiveness of the entities that belong to the functional domain.
In accordance with another aspect of this embodiment of the invention, the grid dimensions corresponding to the same functional domain are the same. In accordance with another aspect of this embodiment of the invention, the grid dimensions corresponding to the same functional domain are determined independent of grid dimensions for different functional domains.
In accordance with another aspect of this embodiment of the invention, the assigning step further comprises the step of calculating a membership value for each entity in each group wherein the membership value is equal to the ratio of intersecting space to total space within the group.
In accordance with another aspect of this embodiment of the invention, the storing step stores the membership values of each entity for each group.
In accordance with another aspect of this embodiment of the invention, the repeating step is performed for only the entities in which a change in conditions has occurred.
In accordance with another embodiment of this embodiment of the invention, a method for dynamically grouping limited range entities in a topological space is disclosed where the method comprises the steps of determining functional domains and range of effectiveness in each functional domain for each entity in the topological space; partitioning the topological space into functional grids wherein each grid corresponds to a unique functional domain and topological space; and assigning each entity to be a member of a group whose range of effectiveness intersects the space of a functional grid and the entity and grid share the same functional domain.
In accordance with another embodiment of this embodiment of the invention, a device to dynamically group limited range entities in a topological space, comprising a data processor; the processor including a domain determiner to ascertain functional domains for each entity in the topological space; a partitioner to separate the topological space into grids for each functional domain; an identifier to assign each grid that has a unique functional domain and topological space to a unique group; a footprint determiner to ascertain the range of effectiveness of each entity for each functional domain that the entity belongs to; a comparator to compare the range of effectiveness of each entity with the space of each group when the entity and group share the same functional domain; an assignor to assign each entity as a member of each group whose range of effectiveness intersects the space of each the group; and a membership storer to store the group memberships in a memory storage device.